Name services have been in use on computer networks for many years. In general, the main function of a name service is to map a name, such as a file name, or network domain name, to some arbitrary data record, such as a file or a network address. A name service can, for example, receive a “look-up request” that includes a name, such as a textual name of a web site, from a requesting client and return information associated with the name, such as the IP address of the web site, to the requesting party. Other functions performed by a name service include mapping a name to a restricted set of data objects. For example, a computerized “white pages” name service for a telephone network might map a person's name to multiple pieces of information, such as the person's telephone number and the person's street address. One of the most popular name services in use today is the Domain Naming Service (DNS).
A name service, like other types of data management systems, may be implemented using a distributed database. That is, some or all of the data records of the name service may be distributed and stored in multiple locations throughout a network. In such a name service, there will often be multiple copies, or “replicas” of any given data record. One challenge that exists in implementing a name service in this manner is providing timely updates to the various replicas of a data record. Another challenge is dealing with so called “flash-crowds.” A flash-crowd is a large number of users who suddenly become interested in a single name or limited set of names administered by the name service and subsequently lose interest after a relatively short period of time. In the context of the DNS and the Internet, for example, a flash-crowd forms when a website suddenly becomes popular, and many users are suddenly and simultaneously entering the domain name of the website (e.g. www.foo.com), thereby causing numerous requests for the IP address of www.foo.com to be sent to DNS servers. A flash-crowd can disrupt name services such as DNS because only a relative few of the name servers on a network will actually have the information required by the flash crowd and will thus be overwhelmed.